package ljl.alg.wangzheng_camp.round1.bfsdfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class _207_can_finish {
    
    // dfs
    static class dfs {
        boolean valid = true;
        List<List<Integer>> edges = new ArrayList<>();
        int[] visited;
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            visited = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                edges.add(new ArrayList<>());
            }
            for (int[] pair : prerequisites) {
                edges.get(pair[0]).add(pair[1]);
            }
            for (int i = 0; i < numCourses && valid; i++) {
                dfs(i);
            }
            return valid;
        }
        void dfs(int i) {
            visited[i] = 1;
            for (int dependent : edges.get(i)) {
                if (visited[dependent] == 0) {
                    dfs(dependent);
                    if (!valid) return;
                } else if (visited[dependent] == 1) {
                    valid = false;
                    return;
                }
            }
            visited[i] = 2;
        }
    }
    
    // bfs 简简单单的拓扑排序
    static class bfs {
        List<List<Integer>> edges = new ArrayList<>();
        int[] in;
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            in = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                edges.add(new ArrayList<>());
            }
            for (int[] each : prerequisites) {
                edges.get(each[1]).add(each[0]);
                in[each[0]]++;
            }
            LinkedList<Integer> q = new LinkedList<>();
            for (int i = 0; i < in.length; i++) {
                if (in[i] == 0)
                    q.add(i);
            }
            int visited = 0;
            while (!q.isEmpty()) {
                visited++;
                for (int dependent : edges.get(q.poll())) {
                    if (--in[dependent] == 0)
                        q.offer(dependent);
                }
            }
            return visited == numCourses;
        }
    }
    
    /*
    * 路飞这个也算是个 dfs
    * */
    static class lufei {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            List<List<Integer>> graph = new ArrayList<>();
            int[] visited = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                graph.add(new ArrayList<>());
            }
            for (int[] each : prerequisites) {
                graph.get(each[1]).add(each[0]);
            }
            for (int i = 0; i < numCourses; i++) {
                if (!dfs(graph, visited, i))
                    return false;
            }
            return true;
        }
        
        boolean dfs(List<List<Integer>> graph, int[] visited, int i) {
            if (visited[i] == 1) return false;
            if (visited[i] == -1) return true;
            visited[i] = 1;
            for (int each : graph.get(i)) {
                if (!dfs(graph, visited, each))
                    return false;
            }
            visited[i] = -1;
            return true;
        }
        
    }
    
}
